class TreeNode(object):
    def __init__(self, val: int):
        self.val = val
        self.height = 0
        self.left = None
        self.right = None

class AvlTree(object):
    def height(self, node):
        if node is not None:
            return node.height
        return -1

    def update_height(self, node):
        node.height = max([self.height(node.left), self.height(node.right)]) + 1

    def balance_factor(self, node):
        if node is None:
            return 0
        return self.height(node.left) - self.height(node.right)

    # AVL旋转，在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡
    # 将平衡因子绝对值>1的节点称为失衡节点，根据失衡情况，旋转分为：右旋、左旋、先右旋后左旋、先左旋后右旋

    # 右旋
    # 将失衡节点为根节点的子树，将该节点记为node，其左子节点记为child，执行右旋
    # 以child为原点，将node向右旋转；然后用child替代以前node的位置
    # 当child有右子节点grand_child时，需要在右旋时将grand_child作为node的左子节点
    def right_rotate(self, node):
        child = node.left
        grand_child = child.right
        child.right = node
        node.left = grand_child
        self.update_height(node)
        self.update_height(child)
        return child

    # 左旋
    # 将失衡节点为根节点的子树，将该节点记为node，其右子节点记为child，执行左旋
    # 以child为原点，将node向左旋转；然后用child替代以前node的位置
    # 当child有左子节点grand_child时，需要在左旋时将grand_child作为node的右子节点
    def left_rotate(self, node):
        child = node.right
        grand_child = child.left
        # 以child为原点，将node向左旋转
        child.left = node
        node.right = grand_child
        # 更新节点高度
        self.update_height(node)
        self.update_height(child)
        return child

    # 四种旋转情况的选择条件
    # 失衡节点的平衡因子           子节点的平衡因子             应采用的旋转方法
    #  > 1(左偏树）                   >= 0                   右旋
    #  > 1(左偏树）                   < 0                    先左旋后右旋
    #  < -1(右偏树）                  <= 0                   左旋
    #  > -1(右偏树）                  > 0                    先右旋后左旋
    def rotate(self, node):
        balance_factor = self.balance_factor(node)
        if balance_factor > 1:
            if self.balance_factor(node.left) >= 0:
                return self.right_rotate(node)
            else:
                node.left = self.left_rotate(node.left)
                return self.right_rotate(node)
        elif balance_factor < -1:
            if self.balance_factor(node.right) <= 0:
                return self.left_rotate(node)
            else:
                node.right = self.right_rotate(node.right)
                return self.left_rotate(node)
        return node

    # AVL树常用操作
    # 插入
    def insert(self, val):
        self._root = self.insert_helper(self._root, val)

    def insert_helper(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self.insert_helper(node.left, val)
        elif val > node.val:
            node.right = self.insert_helper(node.right, val)
        else:
            return node
        self.update_height(node)
        return self.rotate(node)

    # 删除节点
